﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>

//给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。
// 如果一个节点有两个子节点的话，那么该节点的值等于两个子节点中较小的一个。
//
//更正式地说，即 root.val = min(root.left.val, root.right.val) 总成立。
//
//给出这样的一个二叉树，你需要输出所有节点中的 第二小的值 。
//
//如果第二小的值不存在的话，输出 - 1 。
//
//
//
//示例 1：
//
//
//输入：root = [2, 2, 5, null, null, 5, 7]
//输出：5
//解释：最小的值是 2 ，第二小的值是 5 。

int ans;
int rootvalue;

struct TreeNode* dfs(struct TreeNode* node) {
    if (!node) {
        return;
    }
    if (ans != -1 && node->val >= ans) {
        return;
    }
    if (node->val > rootvalue) {
        ans = node->val;
    }
    dfs(node->left);
    dfs(node->right);
};

int findSecondMinimumValue(struct TreeNode* root) {
    ans = -1;
    rootvalue = root->val;
    dfs(root);
    return ans;
}

//在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k + 1 处。
//
//如果二叉树的两个节点深度相同，但 父节点不同 ，则它们是一对堂兄弟节点。
//
//我们给出了具有唯一值的二叉树的根节点 root ，以及树中两个不同节点的值 x 和 y 。
//
//只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true 。否则，返回 false。
//
//
//
//示例 1：
//
//
//输入：root = [1, 2, 3, 4], x = 4, y = 3
//输出：false

// x 的信息
int x_target;
struct TreeNode* x_parent;
int x_depth;
bool x_found;

// y 的信息
int y_target;
struct TreeNode* y_parent;
int y_depth;
bool y_found;

void dfs(struct TreeNode* node, int depth, struct TreeNode* parent) {
    if (!node) {
        return;
    }

    if (node->val == x_target) {
        x_parent = parent;
        x_depth = depth;
        x_found = true;
    }
    else if (node->val == y_target) {
        y_parent = parent;
        y_depth = depth;
        y_found = true;
    }

    // 如果两个节点都找到了，就可以提前退出遍历
    // 即使不提前退出，对最坏情况下的时间复杂度也不会有影响
    if (x_found && y_found) {
        return;
    }

    dfs(node->left, depth + 1, node);

    if (x_found && y_found) {
        return;
    }

    dfs(node->right, depth + 1, node);
}

bool isCousins(struct TreeNode* root, int x, int y) {
    x_target = x;
    y_target = y;
    x_found = false;
    y_found = false;
    dfs(root, 0, NULL);
    return x_depth == y_depth && x_parent != y_parent;
}

